/*
 * @author zzr
 * @date: 2025/10/12  21:17
 * @description: 有一链表的头指针 pHead。给定一 x，编写一段代码将所有小于 x 的节点
 * 排在其余节点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
 */
public class Demo9 {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode pHead, int x) {

        ListNode beforeStart = null;
        ListNode beforeEnd = null;
        ListNode afterStart = null;
        ListNode afterEnd = null;

        ListNode cur = pHead;

        while (cur != null) {
            if (cur.val < x) {
                // 该节点的值在基准 x 的左侧
                if (beforeStart == null) {
                    // 如果 beforeStart 为 null 即第一次插入左侧
                    beforeStart = beforeEnd = cur;
                } else {
                    beforeEnd.next = cur;
                    beforeEnd = beforeEnd.next;
                }
            } else {
                // 该节点的值在基准 x 的右侧
                if (afterStart == null) {
                    // 如果是第一次插入
                    afterStart = afterEnd = cur;
                } else {
                    afterEnd.next = cur;
                    afterEnd = afterEnd.next;
                }
            }
            cur = cur.next;
        }
        // 如果 x 较小，左侧没有节点
        if (beforeStart == null) {
            return afterStart;
        }

        // 连接两个链表
        beforeEnd.next = afterStart;

        // 如果 val 最大的节点不是最后一个节点
        // 需要断开原表的联系，否则容易循环
        if (afterStart != null) {
            afterEnd.next = null;
        }
        return beforeStart;
    }
}
